陈丹琪分治学习笔记

先来看一道模板题:P3810@洛谷 - 【模板】三维偏序(陌上花开)。

考虑 O(n2)O(n^2) 暴力枚举,但是数据范围大到离谱,因此这种方法显然行不通。

下面就来讲解陈丹琪分治算法,主要用于解决 nn 维偏序问题。

前置知识

前置知识

  • 树状数组
  • 函数递归 / 分治
  • 归并排序

偏序问题简述

nn 维偏序,即有 kk 个元素,每个元素有 nn 个属性 ai,1,ai,2,,ai,na_{i,1},a_{i,2},\cdots,a_{i,n},求对于 i[1,k]i\in[1,k],使 aj,1ai,1,aj,2ai,2,,aj,nai,na_{j,1}\le a_{i,1}, a_{j,2}\le a_{i,2}, \cdots, a_{j,n}\le a_{i,n}jij\ne i 的元素个数。

一维偏序问题

一维偏序,即给定 nn 个整数,求对于数 aia_i,满足 ajaia_j\le a_ijij\ne i 的整数个数。

可以考虑排序,复杂度 O(nlogn)O(n\log n)

模板题:P1177@洛谷 - 【模板】快速排序。

二维偏序问题

二维偏序,在平面内有 nn 个点,对于 ii,求 ji,xjxi,yjyij\ne i,x_j\le x_i,y_j\le y_i,此类问题可以考虑树状数组,复杂度 O(nlogn)O(n\log n)

模板题:HDU1541@杭电 - Stars(由于很久以前做的忘记洛谷上那道题的题号了,只能从别人的博客找了外 OJ 的一道题。)

代码:懒得写了,引自[学习笔记]CDQ分治和整体二分

#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=100000+10;
int n,c[maxn],ans[maxn];

struct Stars{
    int x,y;
}a[maxn];

bool cmp(Stars a,Stars b){
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}

inline int read(){
    register int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return (f==1)?x:-x;
}
void add(int x,int y){
    for(;x<maxn;x+=lowbit(x)) c[x]+=y; 
}
int sum(int x){
    int ans=0;
    for(;x;x-=lowbit(x)) ans+=c[x];
    return ans;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++) 
        a[i].x=read(),a[i].y=read();
    sort(a+1,a+n+1,cmp);
    int now;
    for(int i=1;i<=n;i++){
        now=sum(a[i].y+1);
        ans[now]++;
        add(a[i].y+1,1);
    }
    for(int i=0;i<n;i++) 
        printf("%d\n",ans[i]);
    return 0;
}

陈丹琪分治 - 三维偏序问题

简单来讲就只是在上面的二维偏序上面增加一个维度。

我们考虑按第一个属性排序,第二个属性使用归并排序,第三个属性使用树状数组。

归并排序时因为第一个属性有序,因此排序第二个属性时可以随意打乱,因为 aj[mid+1,r]ai[l,mid]a_{j\in[mid+1,r]}\ge a_{i\in[l,mid]}。因为此时两个属性均有序,第三维就可以使用树状数组求解了,复杂度 O(nlog2n)O(n\log^2 n)

模板题:P3810@洛谷 - 【模板】三维偏序(陌上花开)

以下是我的 AC 代码:(当时写的,码风可能不太好)

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;

int n, m;
int ans[MAXN];
struct Node
{
	int a, b, c;
	int w, f;
	bool operator < (const Node &p) const
	{
		if(a != p.a) return a < p.a;
		if(b != p.b) return b < p.b;
		return c < p.c;
	}
}e[MAXN], tmp[MAXN];

namespace BIT
{
	int index[MAXN<<1];
	int lowbit(int x) {return x&(-x);}
	void upd(int x, int y) {for(;x<=m;x+=lowbit(x)) index[x] += y;}
	int sum(int x) {int ans = 0; for(;x;x-=lowbit(x)) ans += index[x]; return ans;}
}
namespace cdq
{
	void mergesort(int l, int mid, int r)
	{
		int x = l, y = mid + 1, tot = l;
		while(x <= mid && y <= r)
		{
			if(e[x].b <= e[y].b) BIT::upd(e[x].c, e[x].w), tmp[tot++] = e[x++];
			else e[y].f += BIT::sum(e[y].c), tmp[tot++] = e[y++];
		}
		while(x <= mid) BIT::upd(e[x].c, e[x].w), tmp[tot++] = e[x++];
		while(y <= r) e[y].f += BIT::sum(e[y].c), tmp[tot++] = e[y++];
		for(int i=l;i<=mid;i++) BIT::upd(e[i].c, -e[i].w);
		for(int i=l;i<=r;i++) e[i] = tmp[i];
	}
	void main(int l, int r)
	{
		int mid = (l + r) >> 1;
		if(l == r) return;
		main(l, mid);
		main(mid+1, r);
		mergesort(l, mid, r);
	}
}

void de_weight(int &cnt)
{
	sort(e+1, e+1+n);
	cnt = 1;
	for(int i=2;i<=n;i++)
	{
		if(e[i].a == e[cnt].a && e[i].b == e[cnt].b && e[i].c == e[cnt].c) ++e[cnt].w;
		else e[++cnt] = e[i];
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>e[i].a>>e[i].b>>e[i].c;
		e[i].w = 1;
		e[i].f = 0;
	}
	int cnt;
	de_weight(cnt);
	cdq::main(1, cnt);
	for(int i=1;i<=cnt;i++) ans[e[i].w+e[i].f-1] += e[i].w;
	for(int i=0;i<n;i++) cout<<ans[i]<<endl;
	return 0;
}

陈丹琪分治套陈丹琪分治 - 四维偏序问题

四维偏序问题也类似,需要陈丹琪分治套陈丹琪分治套树状数组。具体思想类似,在这里不详细讲了,复杂度 O(nlog3n)O(n\log^3 n)

模板题:HDU5126@杭电 - Stars(没错这题也叫 Stars

代码:(还是引自上面那篇博客)

#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=400000+10;
int n,m,mp[maxn],c[maxn],ans[maxn],tot;

struct Element{
    int op,x,y,z,w,id,flag;
}e[maxn],t[maxn],d[maxn];

inline int read(){
    register int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return (f==1)?x:-x;
}
void add(int x,int y){
    for(;x<maxn;x+=lowbit(x)) c[x]+=y;
}
int sum(int x){
    int ans=0;
    for(;x;x-=lowbit(x)) ans+=c[x];
    return ans;
}

void CDQ3d(int l,int r){
    if(l==r) return ;
    int mid=(l+r)>>1;
    CDQ3d(l,mid);CDQ3d(mid+1,r);
    int p=l,q=mid+1,cnt=l;
    while(p<=mid&&q<=r){
        if(t[p].y<=t[q].y){
            if(t[p].op==1&&t[p].flag==0)
                add(t[p].z,1);
            d[cnt++]=t[p++];
        }
        else {
            if(t[q].op==2&&t[q].flag==1)
                ans[t[q].id]+=t[q].w*sum(t[q].z);
            d[cnt++]=t[q++];
        }
    }
    while(p<=mid){
        if(t[p].op==1&&t[p].flag==0)
            add(t[p].z,1);
        d[cnt++]=t[p++];
    }
    while(q<=r){
        if(t[q].op==2&&t[q].flag==1)
            ans[t[q].id]+=t[q].w*sum(t[q].z);
        d[cnt++]=t[q++];
    }
    for(int i=l;i<=mid;i++){
        if(t[i].op==1&&t[i].flag==0)
            add(t[i].z,-1);
    }
    for(int i=l;i<=r;i++) t[i]=d[i];
}

void CDQ2d(int l,int r){
    if(l==r) return ;
    int mid=(l+r)>>1;
    CDQ2d(l,mid);CDQ2d(mid+1,r);
    int p=l,q=mid+1,cnt=l;
    while(p<=mid&&q<=r){
        if(e[p].x<=e[q].x){
            t[cnt++]=e[p++];t[cnt-1].flag=0;
        }
        else {
            t[cnt++]=e[q++];t[cnt-1].flag=1;
        }
    }
    while(p<=mid){
        t[cnt++]=e[p++];t[cnt-1].flag=0;
    }
    while(q<=r){
        t[cnt++]=e[q++];t[cnt-1].flag=1;
    }
    for(int i=l;i<=r;i++) e[i]=t[i];
    CDQ3d(l,r);
}

int main()
{
    int T=read();
    while(T--){
        memset(ans,0,sizeof(ans));
        m=read();tot=0;
        int op,x1,y1,z1,x2,y2,z2,t=0;
        for(int i=1;i<=m;i++){
            op=read();
            if(op==1){
                x1=read(),y1=read(),z1=read();
                e[++tot]=(Element){1,x1,y1,z1,1,tot,0};
            }
            else {
                x1=read(),y1=read(),z1=read(),x2=read(),y2=read(),z2=read();
                t++;
                e[++tot]=(Element){2,x2,y2,z2,1,t,0};
                e[++tot]=(Element){2,x1-1,y2,z2,-1,t,0};
                e[++tot]=(Element){2,x2,y1-1,z2,-1,t,0};
                e[++tot]=(Element){2,x2,y2,z1-1,-1,t,0};
                e[++tot]=(Element){2,x1-1,y1-1,z2,1,t,0};
                e[++tot]=(Element){2,x1-1,y2,z1-1,1,t,0};
                e[++tot]=(Element){2,x2,y1-1,z1-1,1,t,0};
                e[++tot]=(Element){2,x1-1,y1-1,z1-1,-1,t,0};
            }
        }
        for(int i=1;i<=tot;i++) mp[i]=e[i].z;
        sort(mp+1,mp+tot+1);
        int cnt=unique(mp+1,mp+tot+1)-mp-1;
        for(int i=1;i<=tot;i++) e[i].z=lower_bound(mp+1,mp+cnt+1,e[i].z)-mp;
        CDQ2d(1,tot);
        for(int i=1;i<=t;i++) printf("%d\n",ans[i]);
    }
    return 0;
}

高维偏序问题(5\ge5

在更高维的情况下陈丹琪分治也比较慢,基本就是暴力了。可以使用 bitset 优化,复杂度 O(n232)O(\frac{n^2}{32}),这里不详细讲了。